The present invention is generally directed to circuits and methods for use in public key cryptography. Accordingly, the present invention is directed to computations involving modular arithmetic, that is, arithmetic modulo an integer N where N is typically very large and where the result is the remainder after a conventional division by N. More particularly, the present invention is directed to circuits and methods for performing modular reductions, a form of division. Even more particularly, the present invention is directed to circuits and methods for performing multiplication modulo N.
Modular reduction and modular multiplication are two elementary operations that are carried out in most public key cryptography systems. Several techniques are known for performing these operations. For example, to calculate the modular reduction of A modulo N, that is, to determine the remainder when A is divided by N, there are essentially two approaches: the conventional method and the Montgomery method. Both of these methods reduce the number of significant digits of A mod N in a sequential process. The conventional method reduces the number of significant bits in A mod N starting from the most significant digits by a process of division and subtraction. On the other hand, the Montgomery method reduces the number of significant digits using a process of multiplication followed by addition starting instead from the least significant digits. In the conventional method, the quotient of the most significant digits of A divided by N is obtained first. Then the product of the quotient and the modulus N is subtracted from A. The resultant number is the answer if it is less than the modulus. If the resultant number is not less than the modulus, then the division and subtraction process continues. In the Montgomery method, A is added to the product of N and a single digit calculated from the least significant digit of A. The least significant digit of the sum of this addition is zero. Thus, the sum is shifted one digit to the right to remove the least significant digit. In the Montgomery method, these steps are repeated m times, where m is the number of significant digits in N. At the end of the process, the resultant number is (A/Rm) mod N, where R is the value that a single digit can represent. The complex operation of division is not required in the Montgomery method. However, the Montgomery method produces a transformed result. Preprocessing and post processing are required in the Montgomery method to obtain the final result.